package 算法基础模板.chapter_01;

import java.util.Scanner;

/**
 * 二维前缀和
 * <p>
 * S[i, j] = 第i行j列格子左上部分所有元素的和
 *
 * s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + nums[i][j];
 * 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
 * S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
 *
 * @author Summerday
 */
public class MatrixSumT {

    static int m, n, q;
    static int[][] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        q = sc.nextInt(); // 询问的数量
        nums = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                nums[i][j] = sc.nextInt();
            }
        }

        for (int[] n : nums) {
            for (int t : n) {
                System.out.print(t + " ");
            }
            System.out.println();
        }

        int[][] s = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + nums[i][j];
            }
        }
        System.out.println("-------------------------------");
        for (int[] n : s) {
            for (int t : n) {
                System.out.print(t + " ");
            }
            System.out.println();
        }

        while (q-- > 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            //
            int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(sum);
        }


    }

}
